package com.gitee.jsbd.algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序 稳定 O(n)
 * 工作原理：
 * 计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，
 * 比如最大值是 k，我们就可以把数据划分成 k 个桶。
 * 每个桶内的数据值都是相同的，省掉了桶内排序的时间。
 */
public class CountSort {

    public static void countSort(int[] arr) {
        // 计算最大最小值，严谨实现最好用ifPresent检查下
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();

        int N = arr.length;
        int R = max - min + 1; // 最大最小元素之间范围[min, max]的长度
        // 1. 计算频率，在需要的数组长度上额外加1
        int[] count = new int[R + 1];
        for (int i = 0; i < N; i++) {
            // 使用加1后的索引，有重复的该位置就自增
            count[arr[i] - min + 1]++;
        }
        // 2. 频率 -> 元素的开始索引
        for (int r = 0; r < R; r++) {
            count[r + 1] += count[r];
        }

        // 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
        int[] aux = new int[N];
        for (int i = 0; i < N; i++) {
            // 填充一个数据后，自增，以便相同的数据可以填到下一个空位
            aux[count[arr[i] - min]++] = arr[i];
        }
        // 4. 数据回写
        for (int i = 0; i < N; i++) {
            arr[i] = aux[i];
        }
    }

    public static void main(String[] args) {
        // 排序前数组
        int[] data = new int[]{5, 8, 7, 9, 1, 2, 3, 8, 2, 1, 0, 10, 11, 44, 5};
        System.out.print("==初始化==：");
        System.out.println(Arrays.toString(data));

        countSort(data);
        System.out.println(Arrays.toString(data));
    }

}
